#pragma GCC optimize(2)
#include <bits/stdc++.h>

using namespace std;
#define int long long
const int inf = 0x3f3f3f3f3f3f3f3f;

vector<int> p;

int qpow(int a, int b)
{
	int ret = 1;
	while (b > 0)
	{
		if (b & 1)
			ret = ret * a;
		a = a * a;
		b >>= 1;
	}
	return ret;
}

void solve()
{
	int n, k;
	cin >> n >> k;
	int coin = 0;
	priority_queue<int> q;
	{
		int x = n;
		while (x)
		{
			int it = lower_bound(p.begin(), p.end(), x) - p.begin();
			if (it == p.size())
			{
				cout << -1 << '\n';
				return;
			}
			if (p[it] != x) --it;
			if (it != 0) q.push(it);
			coin += qpow(3, it + 1) + it * qpow(3, it - 1);
			x -= p[it];
			k--;
		}
		if (k < 0)
		{
			cout << -1 << '\n';
			return;
		}
	}
	// 3^(x+1) + x * 3^(x-1)
	while (k > 1 && q.size())
	{
		int x = q.top();
		q.pop();
		k -= 2;
		coin -= qpow(3, x - 1);
		if (x - 1 != 0)
		{
			q.push(x - 1);
			q.push(x - 1);
			q.push(x - 1);
		}
	}
	cout << coin << '\n';
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int i = 1;
	while (i <= 1e18)
	{
		p.push_back(i);
		i *= 3;
	}
	int _ = 1;
	cin >> _;
	while (_--)
	{
		solve();
	}
	return 0;
}